package com.Questions.DP;


/**
 * 打家劫舍
 */
public class leetcode198 {
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;++i){
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[nums.length-1];
    }
    // 在第i个房间 可以选择偷和不偷
    // 如果偷 则i-1不能偷 那么收益就是nums[i]+dp[i-2]
    // 如果不偷 则收益就是 dp[i-1]
    // dp[i]=max{nums[i]+dp[i-2],dp[i-1]}
    // 注意经验总结 如果动态规划维护的数组 和前两个元素 有关 那么
    // 在这个一维数组上 必然有两个初值 才能保证初始条件
}
